package com.test.daily.leetcode.y2021.m10.day1005;

/**
 * findMedianSortedArrays
 *
 * @author Tom on 2021/10/5
 */
public class Algo02_FindMedianSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2};
        int[] nums2 = new int[]{3,4};
        double average = findMedianSortedArrays(nums1, nums2);
        System.out.println("average:" + average);
//        System.out.println("3/2=" + 4/2);
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2){
        int nums1Length = nums1.length;
        int nums2Length = nums2.length;
        int totalLength = nums1Length + nums2Length;
        if(totalLength % 2 == 1){
            return getMedianNumber(nums1, nums2, totalLength / 2 + 1);
        }else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            return (getMedianNumber(nums1, nums2, midIndex1 + 1) + getMedianNumber(nums1, nums2, midIndex2+1))/2.0;
        }
    }
    public static double getMedianNumber(int[] nums1, int[] nums2, int k){
        int index1 = 0, index2 = 0;
        int length1 = nums1.length;
        int length2 = nums2.length;
        while(true){
            if(index1 == length1){
                return nums2[index2 + k - 1];
            }
            if(index2 == length2){
                return nums1[index1 + k -1];
            }
            if(k == 1){
                return Math.min(nums1[index1], nums2[index2]);
            }
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if(pivot1 <= pivot2){
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            }else{
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}
